package com.zhao.leetcode.linked;

/**
 * 删除链表的倒数第N个节点
 *
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/?envType=study-plan-v2&envId=top-interview-150
 *
 * 19. 删除链表的倒数第 N 个结点
 * 提示
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 */
public class DeleteNNode {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode two = new ListNode(2);
//        ListNode three = new ListNode(3);
//        ListNode four = new ListNode(4);
//        ListNode five = new ListNode(5);
//        four.next = five;
//        three.next = four;
//        two.next = three;
//        head.next = two;

        DeleteNNode node = new DeleteNNode();
        node.removeNthFromEndV2(head, 1);

    }

    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode opeHead = head;

        ListNode index = head;

        while (n > 0) {
            index = index.next;
            n -- ;
        }
        if(index == null) {
            return opeHead.next;
        }
        while (index.next != null) {
            opeHead = opeHead.next;
            index = index.next;
        }
        opeHead.next = opeHead.next.next;

        return head;
    }

    public ListNode removeNthFromEndV2(ListNode head, int n) {

        ListNode slow = head, fast = head;
        while (n > 0) {
            fast = fast.next;
            n --;
        }
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        if (fast == null) {
            return slow.next;
        }

        if(slow.next != null && slow.next.next != null) {
            slow.next = slow.next.next;
            return head;
        }

        slow.next = null;
        return head;

    }


}
